package com.company.Algorihm;

import org.omg.PortableInterceptor.INACTIVE;

import java.util.Arrays;

/**
 * @author VX5
 * @Title: MJC
 * @ProjectName DataStructure
 * @Description: TODO
 * @date ${DAT}9:41
 */
public class PrimAlgorithm {
    public static void main(String[] args) {
        char[] data = new char[]{'A','B','C','D','E','F','G'};
        int verxs = data.length;
        //邻接矩阵的关系使用二维数组表示,10000这个大数，表示两个点不联通
        int [][]weight=new int[][]{
                {10000,5,7,10000,10000,10000,2},
                {5,10000,10000,9,10000,10000,3},
                {7,10000,10000,10000,8,10000,10000},
                {10000,9,10000,10000,10000,4,10000},
                {10000,10000,8,10000,10000,5,4},
                {10000,10000,10000,4,5,10000,6},
                {2,3,10000,10000,4,6,10000},};

        //创建MGraph对象
        MGraph graph = new MGraph(verxs);
        //创建一个MinTree对象
        MinTree minTree = new MinTree();
        minTree.creatMGraph(graph, verxs, data, weight);
        //输出
        minTree.showGraph(graph);
        minTree.prim(graph,0);
    }

    //创建最小生成树
    static class MinTree{
        public void creatMGraph(MGraph mGraph,int verxs,char[] data,int[][] weight){
            int i,j;
            for (i=0;i<verxs;i++){
                mGraph.data[i] = data[i];
                for (j = 0;j < weight[i].length;j++) {
                    mGraph.weight[i][j] =weight[i][j];
                }
            }
        }

        //编写prim算法，得到最小生成树

        /**
         *
         * @param graph
         * @param v 表示从图的第几个定点开始生成 A-》0 、B-》1
         */
        public void prim(MGraph graph,int v){
            int[] visited = new int[graph.verxs];//标记节点是否访问过  默认都是0

            //把当前这个节点标记为已访问
            visited[v] = 1;
            int h1 = -1;
            int h2 = -1;//h1\h2记录两个顶点的下标
            int minWeight = 10000;//初始化一个大数，后面遍历过程中，会被替换
            for (int k = 1; k < graph.verxs;k++){
                for (int i = 0; i < graph.verxs;i++){//一个点连接其他点
                    for (int j = 0; j < graph.verxs;j++){
                        if (visited[i] == 1 && visited[j] == 0 && graph.weight[i][j] < minWeight){
                            minWeight = graph.weight[i][j];
                            h1 = i;
                            h2 = j;
                        }
                    }
                }
                System.out.println("找到最短路径："+graph.data[h1]+","+graph.data[h2]+":"+minWeight);
                visited[h2] = 1;//在这标记是因为找到合适的才下手
                minWeight = 10000;//还原权值指标
            }

        }

        public void showGraph(MGraph graph){
            for (int[] link:graph.weight){
                System.out.println(Arrays.toString(link));
            }
        }
    }

    //图的实体类
    static class MGraph{
        int verxs;
        char[] data;
        int[][] weight;

        public MGraph(int verxs) {
            this.verxs = verxs;
            data = new char[verxs];
            weight = new int[verxs][verxs];
        }
    }
}
